//Mon Aug  1 17:09:24 IST 2011

#include <stdio.h>
#include <stdlib.h>

typedef struct listtag {
	int value;

	struct listtag *next;
}list;


void recursive_list_free (list *head)
{
	list *temp;
	while (head) {
		temp = head->next;
		free (head);
		head = temp;
	}
}

void recursive_list_print (list *head)
{
	printf ("List printing begins \n");
	while (head) {
		printf ("%d\t", head->value);
		head = head->next;
	}
}

list * add_to_list (list *head, int value)
{
	list *lnode;

	lnode = malloc (sizeof(list));
	lnode->value = value;

	if (head)
		lnode->next = head;
	else
		lnode->next = NULL;

	return lnode;
}


typedef struct node {
	int value;

	struct node* left;
	struct node* right;
}tree;

tree * insert (tree * root, int value)
{
	tree *node;
	if (!root) {
		node = malloc(sizeof(tree));
		node->value = value;
		node->left = node->right = NULL;
		return node;
	}

	tree *active, *prev;
	active = root;

	while (active) {

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else {
			printf ("%d element already exists\n", value);
			return root;
		}
	}

	node = malloc(sizeof(tree));
	node->value = value;
	node->left = node->right = NULL;

	if (prev->value < value)
		prev->right = node;
	else
		prev->left = node;

	return root;
}

tree * search (tree *root, int value)
{
	if (!root) {
		printf ("Tree is empty\n");
		return NULL;
	}

	tree *active;
	active = root;

	while (active) {

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else if (active->value == value) {
			printf ("match found %d\n", value);
			return active;
		}
	}

	printf ("element %d not found\n", value);

	return NULL;
}

tree * delete (tree *root, int value)
{
	if (!root) {
		printf ("delete call for element [%d] in an empty tree\n", value);
		return NULL;
	}

	tree *active, *prev = NULL;
	active = root;

	while (active) {

		if (active->value == value)
			break;

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
	}

	if (!active) {
		printf ("element not found in the tree\n");
		return root;
	}

	if (!active->left && !active->right) {
		// Leaf Node
		if (prev) {
			if (prev->left == active)
				prev->left = NULL;
			else
				prev->right = NULL;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			printf ("root was the element we searched for and there are no other elements in the tree. emptied the tree.\n");
			printf ("element %d deleted\n", value);
			free (active);
			return NULL;
		}
	}

	// Only left child
	if (active->left && !active->right) {
		if (prev) {
			if (prev->left == active)
				prev->left = active->left;
			else
				prev->right = active->left;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			tree *temp;

			printf ("root was the element we searched for. making the left child as the new root\n");
			printf ("element %d deleted\n", value);
			temp = active->left;
			free (active);
			return temp;
		}
	}

	//Only right child
	if (!active->left && active->right) {
		if (prev) {
			if (prev->left == active)
				prev->left = active->right;
			else
				prev->right = active->right;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			tree *temp;

			printf ("root was the element we searched for. making the right child as the new root\n");
			printf ("element %d deleted\n", value);
			temp = active->left;
			free (active);
			return temp;
		}
	}

	//Both children exist
	tree *temp;

	prev = NULL;
	temp = active->right;
	while (temp->left) {
		prev = temp;
		temp = temp->left;
	}

	active->value = temp->value;
	if (prev) {
		prev->left = NULL;
	} else {
		active->right = temp->right;
	}
	printf ("element %d deleted\n", value);
	free (temp);

	return root;
}

int find_depth (tree *active)
{
	int lh = 0, rh = 0;

	if (active->left)
		lh = 1 + find_depth (active->left);
	if (active->right)
		rh = 1 + find_depth (active->right);

	if (lh > rh)
		return lh;
	else
		return rh;
}


int check_if_tree_is_balanced (tree *t)
{
	int lh, rh;

	lh = rh = 0;
	
	if (t->left)
		lh = 1 + find_depth (t->left);

	if (t->right)
		rh = 1 + find_depth (t->right);

	printf ("Left subtree length: %d\n", lh);
	printf ("Right subtree length: %d\n", rh);

	if (abs(rh-lh) >= 2)
		printf ("Imbalanced Tree");
	else
		printf ("Balanced Tree");

	return 0;
}

void in_order_traversal (tree *root)
{
	if (!root)
		return;

	if (root->left)
		in_order_traversal (root->left);

	printf ("%d\t", root->value);

	if (root->right)
		in_order_traversal (root->right);

	return;
}

/* Returns the maximum height of the tree.
 * The nodes corresponding to the longest path is stored in the
 * list handled to by the cur pointer (Note the **).
 */
int find_longest_path (tree *t, int height, list **cur)
{
	if (!t)
		return 0;
	
	list *llist, *rlist;
	int lh, rh;

	llist = rlist = NULL;
	lh = rh = -1;

	if (t->left)
		lh = find_longest_path (t->left, height + 1, &llist);

	if (t->right)
		rh = find_longest_path (t->right, height + 1, &rlist);

	if (lh == -1 && rh == -1) {
		*cur = add_to_list (NULL, t->value);
		return 1;
	} else if (lh > rh) {
		recursive_list_free (rlist);
		*cur = add_to_list (llist, t->value);
		return lh + 1;
	} else {
		/* will prefer the right subtree in case both
		 * the left and right subtrees are of equal height
		 */
		recursive_list_free (llist);
		*cur = add_to_list (rlist, t->value);
		return rh + 1;
	}
}

int main ()
{
	tree *t;

	t = insert (NULL, 50);
	t = insert (t, 17);
	t = insert (t, 76);
	t = insert (t, 9);
	t = insert (t, 23);
	t = insert (t, 54);
	t = insert (t, 14);
	t = insert (t, 19);
	t = insert (t, 72);
	t = insert (t, 12);
	//t = insert (t, 67);


	list *path = NULL;
	int height;

	height = find_longest_path (t, 0, &path);
	printf ("Max height is: %d\n", height);
	recursive_list_print (path);

#if 0

	printf ("\n");
	in_order_traversal (t);
	printf ("\n");

	check_if_tree_is_balanced (t);

	t = delete (t, 4);
	printf ("new root is : %d\n", t->value);

	tree *temp;

	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 3);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 2);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 5);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 9);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 12);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);

	t = delete (t, 1);
	temp = search (t, 1);
	temp = search (t, 2);
	temp = search (t, 5);
	temp = search (t, 9);
#endif
	return 0;
}
//Mon Aug  1 18:46:26 IST 2011
